#include "superheader.h"

InputData inputData;

void outputProtocol(const QString        name,
                    const QVector<bool>& opennessHubs,
                    const QVector<bool>& matrixConnections);
void removalAlgorithm();

int main()
{
  removalAlgorithm();
  return 0;
}

/*
  Инициализация алгоритма Ежи-Вильямса
  Выход: матрица выгоды каналов
*/
QVector<double> initializationMatrixT() {
  QVector<double> matrixT(inputData.numberOfTerminals * inputData.numberOfHubs);
  for (int i = 0; i < inputData.numberOfTerminals; ++i) {
    for (int j = 0; j < inputData.numberOfHubs; ++j) {
      matrixT[i * inputData.numberOfHubs + j] =
          inputData.matrixCostChannels[i * inputData.numberOfHubs + j] -
          inputData.matrixCostChannels[i * inputData.numberOfHubs];
    }
  }
  return matrixT;
}

/*
  Шаг 1 в алгоритме Ежи-Вильямса
  Вход:  матрица выгоды каналов, вектор открытости каналов
  Выход: индекс лучшего из доступных каналов
*/
int step1(const QVector<double>& matrixT, const QVector<bool>& opennessHubs) {
  double min = matrixT[0]; // степень выгоды (чем меньше тем лучше)
  int minI = 0, minJ = 0;

  // поиск минимума
  for (int i = 0; i < inputData.numberOfTerminals; ++i) {
    for (int j = 0; j < inputData.numberOfHubs; ++j) {
      if (opennessHubs[j]) {
        // предпочесть канал соединяющий сразу с центральным узлом
        if (minI != 0 && min == matrixT[i * inputData.numberOfHubs + j] && i == 0) {
          min  = matrixT[i * inputData.numberOfHubs + j];
          minI = i;
          minJ = j;
        }
        else if (min > matrixT[i * inputData.numberOfHubs + j]) {
          min  = matrixT[i * inputData.numberOfHubs + j];
          minI = i;
          minJ = j;
        }
      }
    }
  }

  return minI * inputData.numberOfHubs + minJ;
}

/*
  Шаг 2 в алгоритме Ежи-Вильямса
  Вход:  индекс лучшего канала, матрица выгоды каналов, вектор оставшиеся свободных входов
  Выход: возможность использовать канал (true - можно)
*/
bool step2(const int ind, QVector<double>* matrixT, QVector<int>* freeIn) {
  bool res = freeIn->at(ind % inputData.numberOfHubs) > 0;
  if (res) {
    --(*freeIn)[ind % inputData.numberOfHubs];
  }
  else {
    (*matrixT)[ind] = 8; // 8 в роли бесконечности
  }
  return res;
}

/*
  Шаг 3 в алгоритме Ежи-Вильямса
  Вход: индекс лучшего канала, матрица выгоды каналов, матрица соединений
*/
void step3(int ind, QVector<double>* matrixT, QVector<bool>* matrixConnections) {
  // добавить использовать канал для соединения
  (*matrixConnections)[ind] = true;
  // исключить подключенный терминал из дальнейшего рассмотрения
  int i = ind / inputData.numberOfHubs;
  for (int j = 0; j < inputData.numberOfHubs; ++j) {
    (*matrixT)[i * inputData.numberOfHubs + j] = 8; // 8 в роли бесконечности
  }
}

/*
  Алгоритм Ежи-Вильямса
  вход:  массив открытости концентраторов
  выход: матрица соединений
*/
QVector<bool> ezhyWilliams(const QVector<bool>& opennessHubs) {
  QVector<bool>   matrixConnections;                        // матрица соединений
  QVector<int>    freeHubsCapacity(inputData.hubsCapacity); // оставшиеся свободные входы
  QVector<double> matrixT;                                  // матрица выгоды каналов
  int             ind;                                      // индекс канала с наибольшей
                                                            // выгодой

  matrixConnections.fill(false, inputData.numberOfTerminals * inputData.numberOfHubs);
  matrixT = initializationMatrixT();
  while ( matrixT[ind = step1(matrixT, opennessHubs)] <= 0.0 ) {
    if ( step2(ind, &matrixT, &freeHubsCapacity) ) {
      step3(ind, &matrixT, &matrixConnections);
    }
  }

  return matrixConnections;
}

/*
  Целевая функция
  Вход:  вектор открытости концентраторов, матрица соединений
  Выход: стоимость сети
*/
double targetFunction(const QVector<bool>& opennessHubs,
                      const QVector<bool>& matrixConnections) {
  double res = 0.0;
  // стоимость концентраторов
  for (int j = 0; j < opennessHubs.size(); ++j) {
    if (opennessHubs[j]) {
      res += inputData.hubsCost[j];
    }
  }

  // стоимость каналов
  for (int ind = 0; ind < matrixConnections.size(); ++ind) {
    if (matrixConnections[ind]) {
      res += inputData.matrixCostChannels[ind];
    }
  }
  return res;
}

/*
  Поиск в hash таблице минимального значения
  Вход:  hash таблица
  Выход: индекс минимального значения
*/
int minimum(QHash<int, double>& hash) {
  QHash<int, double>::iterator it = hash.begin();
  double min = it.value();
  int ind = it.key();

  for (++it; it != hash.end(); ++it) {
    if (it.value() < min) {
      min = it.value();
      ind = it.key();
    }
  }
  return ind;
}

/*
  Вывод матрицы
*/
template <class T>
void outputMatrix(const QString& name, const T& matrix, const int rows, const int columns) {
  cout << name.toStdString();
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < columns; ++j) {
      cout << "\t" << matrix[i * columns + j];
    }
    cout << endl;
  }
}

/*
  Вывод результата на экран
  Вход: заголовок, вектор открытости концентраторов, матрица соединений
*/
void outputProtocol(const QString        title,
                    const QVector<bool>& opennessHubs,
                    const QVector<bool>& matrixConnections) {
  cout << title.toStdString();
  outputMatrix("матрица стоимостей линий связи:\n", inputData.matrixCostChannels,
               inputData.numberOfTerminals,         inputData.numberOfHubs);
  outputMatrix("открытость концентраторов:\n",      opennessHubs,
               1,                                   opennessHubs.size());
  outputMatrix("матрица соединений:\n",             matrixConnections,
               inputData.numberOfTerminals,         inputData.numberOfHubs);
  cout << "стоимость сети: " << targetFunction(opennessHubs, matrixConnections) << "\n\n\n";
}

/*
  Алгоритм удаления
  */
void removalAlgorithm() {
  // инициализация
  QVector<bool> opennessHubs(inputData.numberOfHubs, true);      // все концентраторы открыты
  QVector<bool> matrixConnections = ezhyWilliams(opennessHubs);  // терминалы подключены к
                                                                 // "ближайшему" концентратору
  QHash<int, double> savedCosts;                                 // массив целевых функций
  double cost = targetFunction(opennessHubs, matrixConnections); // целевая функция
  double tempCost;
  int    iterate = 1; // номер итерации

  outputProtocol("\t\tНачало!\n\n", opennessHubs, matrixConnections);
  do { // цикл по итерациям алгоритма
    int i = 0; // номер концентратора, надо учесть что центральный узел пропускается
    do { // цикл по открытым концентраторам
      for (++i; i < opennessHubs.size() && !opennessHubs[i]; ++i); // пропустить закрытые
                                                                   // концентраторы
      if ( i < opennessHubs.size() ) { // если концентраторы не кончились
        opennessHubs[i]   = false;
        matrixConnections = ezhyWilliams(opennessHubs);
        tempCost          = targetFunction(opennessHubs, matrixConnections);
        outputProtocol("\t\tИтерация #" + QString().number(iterate++) + "\n\n",
                       opennessHubs, matrixConnections);
        if (tempCost <= cost) { // если результат приемлемый
          savedCosts.insert(i, tempCost); // сохраняется номер терминала и стоимость сети
        }
        opennessHubs[i] = true;
      } else {
        break; // рассмотрены все открытые терминалы
      }
    } while (1);

    if ( savedCosts.isEmpty() ) { // если приемлемых результатов нету
      matrixConnections = ezhyWilliams(opennessHubs); // итоговая конфигурация сети
      outputProtocol("\t\tИтог!\n\n", opennessHubs, matrixConnections);
      break;
    } else {
      i               = minimum(savedCosts); // выбор лучшего результата
      opennessHubs[i] = false;
      cost            = savedCosts.value(i, -1.0);
    }
    savedCosts.clear();
  } while (1);
}
